//*******************************************************************
//  LinkedBinaryTree.java       Java Foundations
//
//  Implements a binary tree using a linked representation.
//*******************************************************************



import java.util.Iterator;

public class LinkedBinaryTree<T> implements BinaryTree<T>
{
   public BTNode<T> root;
   LinkedBinaryTree<T> left;
   LinkedBinaryTree<T> right;

   //-----------------------------------------------------------------
   //  Creates an empty binary tree.
   //-----------------------------------------------------------------
   public LinkedBinaryTree()
   {
      root = null;
      left=null;
      right=null;
   }

   //-----------------------------------------------------------------
   //  Creates a binary tree with the specified element as its root.
   //-----------------------------------------------------------------
   public LinkedBinaryTree (T element)
   {
      root = new BTNode<T>(element);
      left=null;
      right=null;
   }

   //-----------------------------------------------------------------
   //  Creates a binary tree with the two specified subtrees.
   //-----------------------------------------------------------------
   public LinkedBinaryTree (T element, LinkedBinaryTree<T> left,
      LinkedBinaryTree<T> right)
   {
      root = new BTNode<T>(element);
      root.setLeft(left.root);
      root.setRight(right.root);
   }

   //-----------------------------------------------------------------
   //  Returns the element stored in the root of the tree. Throws an
   //  EmptyCollectionException if the tree is empty.
   //-----------------------------------------------------------------
   public T getRootElement()
   {
      if (root == null)
         throw new EmptyCollectionException ("Get root operation "
            + "failed. The tree is empty.");

      return root.getElement();
   }

   //-----------------------------------------------------------------
   //  Returns the left subtree of the root of this tree.
   //-----------------------------------------------------------------
   public LinkedBinaryTree<T> getLeft()
   {
      if (root == null)
         throw new EmptyCollectionException ("Get left operation "
            + "failed. The tree is empty.");

      LinkedBinaryTree<T> result = new LinkedBinaryTree<T>();
      result.root = root.getLeft();

      return result;
   }
   public void setLeft(LinkedBinaryTree item){
      root.setLeft(item.root);
   }
   public void setRight(LinkedBinaryTree item){
      root.setRight(item.root);
   }
   public void setTree(T element){
      root = new BTNode<>(element);
   }
   public void setTree(T element,LinkedBinaryTree<T> lefttree,LinkedBinaryTree<T> rightTree){
       root = new BTNode<>(element);
       if(lefttree != null && !lefttree.isEmpty()){
           root.setLeft(lefttree.root.copy());
       }

       if(rightTree != null && !rightTree.isEmpty()){
           root.setRight(rightTree.root.copy());
       }
   }
   public void setTree(LinkedBinaryTree<T> leftTree,LinkedBinaryTree<T> rightTree){
      root=this.root;
      if(leftTree != null && !leftTree.isEmpty()){
         root.setLeft(leftTree.root.copy());
      }

      if(rightTree != null && !rightTree.isEmpty()){
         root.setRight(rightTree.root.copy());
      }
   }
   @Override
   public boolean contains(T target) {
      BTNode<T> node = null;
      if (root!=null)
         node = root.find(target);
      if (node==null)
         return false;
      else return true;
   }

   //-----------------------------------------------------------------
   //  Returns the element in this binary tree that matches the
   //  specified target. Throws a ElementNotFoundException if the
   //  target is not found.
   //-----------------------------------------------------------------
   public T find (T target)
   {
      BTNode<T> node = null;

      if (root != null)
         node = root.find(target);

      if (node == null)
         throw new ElementNotFoundException("Find operation failed. "
            + "No such element in tree.");

      return node.getElement();
   }

   @Override
   public boolean isEmpty() {

      if (root==null){
         return true;
      }
      else return false;
   }

   //-----------------------------------------------------------------
   //  Returns the number of elements in this binary tree.
   //-----------------------------------------------------------------
   public int size()
   {
      int result = 0;

      if (root != null)
         result = root.count();

      return result;
   }

   @Override
   public Iterator<T> preorder() {
      ArrayIterator<T> iter = new ArrayIterator<>();
      if (root!=null)
         root.preorder(iter);
      return iter;
   }
   public Iterator<T> inorder()
   {
      ArrayIterator<T> iter = new ArrayIterator<T>();
      if (root != null)
         root.inorder (iter);
      return iter;
   }

   @Override
   public Iterator<T> postorder() {
      ArrayIterator<T> iter = new ArrayIterator<>();
      if (root!=null)
         root.postorder(iter);
      return iter;
   }

   //-----------------------------------------------------------------
   //  Populates and returns an iterator containing the elements in
   //  this binary tree using a levelorder traversal.
   //-----------------------------------------------------------------
   public Iterator<T> levelorder()
   {
      LinkedQueue<BTNode<T>> queue = new LinkedQueue<BTNode<T>>();
      ArrayIterator<T> iter = new ArrayIterator<T>();

      if (root != null)
      {
         queue.enqueue(root);
         while (!queue.isEmpty())
         {
            BTNode<T> current = queue.dequeue();

            iter.add (current.getElement());

            if (current.getLeft() != null)
               queue.enqueue(current.getLeft());
            if (current.getRight() != null)
               queue.enqueue(current.getRight());
         }
      }

      return iter;
   }

   //-----------------------------------------------------------------
   //  Satisfies the Iterable interface using an inorder traversal.
   //-----------------------------------------------------------------
   public Iterator<T> iterator()
   {
      return inorder();
   }

   //-----------------------------------------------------------------
   //  The following methods are left as programming projects.
   //-----------------------------------------------------------------
    public LinkedBinaryTree<T> getRight() {
      if (root==null)
         throw new EmptyCollectionException("Get right operation"+"failed.The tree is empty.");
      LinkedBinaryTree<T> result = new LinkedBinaryTree<>();
      result.root=root.getRight();
      return result;
    }
   public  BTNode<T> CreatTree(T [] pre,T [] inorder){
      if (pre.length==0||inorder.length==0||pre.length!=inorder.length){
         return null;
      }
      BTNode<T> mTree = new BTNode<>(pre[0]);
      int num = Findpostion(pre[0],inorder);
      T[] preLeft =  (T[])(new Object[num]);
      T[] inorderLeft = (T[])(new Object[num]);
      T[] preRight = (T[])(new Object[pre.length-num-1]);
      T[] inorderRight = (T[])(new Object[inorder.length-num-1]);
      for(int j =0;j<inorder.length;j++){
         if (j<num){
            preLeft[j] = pre[j+1];
            inorderLeft[j] = inorder[j];
         }
         else if (j>num){
            preRight[j-num-1]=pre[j];
            inorderRight[j-num-1]=inorder[j];
         }
      }
      mTree.left= CreatTree(preLeft,inorderLeft);
      mTree.right = CreatTree(preRight,inorderRight);
      return mTree;
   }
   /*
   public static Object [] getArray(Object [] pre,Object [] inorder,int num){
      int i = Findpostion(pre[0],pre);
      int rightlength1 = pre.length-i-1;
      int rightlength2 = inorder.length-i-1;
      Object [] item =new Object[i];
      Object [] item1 =new Object[rightlength1];
      Object [] item2 = new Object[rightlength2];
      switch (num){
         case 0:
            for (int j=0;j<i;j++){
               item[j] = pre[j+1];
            }
            return item;

         case 1:
            for (int j=0;j<i;j++){
               item[j] = inorder[j];
            }
            return item;

         case 2:
            for (int j =i+1;j<inorder.length;j++){
               item1[j-i-1]=pre[j];
            }
            return item1;

         default:
            for (int j =i+1;j<inorder.length;j++){
               item2 [j-i-1]=inorder[j];
            }
            return item2;
      }

   }
   */
   public static int Findpostion(Object num,Object arr []){
      int i =0;
     while (arr[i]!= num){
        i++;
     }
      return i;
   }
   //计算树
   public int calculate(){
      StringBuilder mBuilder = new StringBuilder();
      MyDC myDC = new MyDC();
      ArrayIterator<T> mIterator = (ArrayIterator<T>) this.postorder();
      while (mIterator.hasNext()){
         mBuilder.append(mIterator.next());
         mBuilder.append(" ");
      }
      return myDC.evaluate(String.valueOf(mBuilder)) ;
   }
   }

